package cn.arnold.array;

/**
 * 二维数组实现稀疏数组
 */
public class SparseArray {
    /**
     * 二维数组转稀疏数组
     * @return
     */
    public static int[][] toSparseArray(int[][] array) {
        // 获取二维数组行数
        int row = array.length;
        // 获取列
        int column = array[0].length;
        // 遍历原始的二维数组，获取有用的元素个数 sum
        int sum = 0;
        for (int[] ints : array) {
            for (int j = 0; j < column; j++) {
                if (ints[j] != 0) {
                    sum++;
                }
            }
        }
        // 根据sum创建稀疏数组
        int[][] sparseArray = new int[sum + 1][3];
        // 第一行赋值
        sparseArray[0][0] = row;
        sparseArray[0][1] = column;
        sparseArray[0][2] = sum;
        // 遍历二维数组，将有效元素赋值给稀疏数组
        int count = 0;    //记录有效元素的个数
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (array[i][j] != 0) {
                    count++;
                    sparseArray[count][0] = i;    //  非零元素的行数
                    sparseArray[count][1] = j;    //  非零元素的列数
                    sparseArray[count][2] = array[i][j]; // 非零元素的值
                }
            }
        }
        return sparseArray;
    }

    /**
     * 稀疏数组转二维数组
     */
    public static int[][] toArray(int[][] sparseArray) {
        // 读取稀疏数组的第一行
        int row = sparseArray[0][0];
        int column = sparseArray[0][1];
        int sum = sparseArray[0][2];
        // 创建二维数组
        int[][] array = new int[row][column];
        // 将有效元素映射到二维数组
        for (int i = 1; i < sparseArray.length; i++) {
            array[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }
        return array;
    }
}


